package code1_100.code1_10;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 *
 * 输入：s = "cbbd"
 * 输出："bb"
 *
 */
public class _5longestPalindrome {

    /**
     * 第一种方法，从每个字符的中心进行判定
     * @param s
     * @return
     */
    public static String longestPalindrome1(String s) {
        // 初始以为记录最长回文串的长度，定义了此变量
        int result = 0;
        // 记录字符串长度
        int length = s.length();
        // 记录最长回文串的左起始点，最终返回起始点加长度即可
        int leftCur = 0;
        for (int i = 0; i < length; i++) {
            int left = i-1;
            int right = i+1;
            int paLength = 1;
            while(left>=0&&s.charAt(left)==s.charAt(i)){
                left--;
                paLength++;
            }
            while(right<length&&s.charAt(right)==s.charAt(i)){
                right++;
                paLength++;
            }
            while(left>=0&&right<length&&s.charAt(left)==s.charAt(right)) {
                left--;
                right++;
                paLength+=2;
            }
            if(result<paLength){
                leftCur = left+1;
                result = paLength;
            }
        }
        return s.substring(leftCur,leftCur+result);
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("cbbd"));
    }

    /**
     *  动态规划求解
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        int len = s.length();
        if(len<2)return s;
        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示s[i,j]是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化，所有长度为1的字串都是回文串
        for(int i = 0;i<len;i++){
            dp[i][i] = true;
        }
        char[] charArray = s.toCharArray();
        // 开始进行递推
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上线设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由L和i可以确定右边界
                int j = L+i-1;
                // 如果右边界越界，则退出当前循环
                if(j>=len)break;
                if(charArray[i]!=charArray[j]){
                    dp[i][j] = false;
                }else {
                    if(j-i<3){
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                // 只要dp[i][L]==true成立，就表示字串为回文串
                if(dp[i][j]&&j-i+1>maxLen){
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }

}
